{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Distance Between BST Nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDiffInBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉搜索树节点最小距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二叉搜索树的根节点 <code>root</code> ，返回 <strong>树中任意两不同节点值之间的最小差值</strong> 。</p>\n",
    "\n",
    "<p>差值是一个正数，其数值等于两值之差的绝对值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/05/bst1.jpg\" style=\"width: 292px; height: 301px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [4,2,6,1,3]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/05/bst2.jpg\" style=\"width: 282px; height: 301px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,0,48,null,null,12,49]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目范围是 <code>[2, 100]</code></li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题与 530：<a href=\"https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/\">https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/</a> 相同</p>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-distance-between-bst-nodes](https://leetcode.cn/problems/minimum-distance-between-bst-nodes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-distance-between-bst-nodes](https://leetcode.cn/problems/minimum-distance-between-bst-nodes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,6,1,3]', '[1,0,48,null,null,12,49]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = float('inf')\n",
    "        self.pre = None\n",
    "\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "\n",
    "        self.traverse(root.left)\n",
    "        if self.pre:\n",
    "            self.res = min(abs(self.pre.val - root.val), self.res)\n",
    "        self.pre = root\n",
    "        self.traverse(root.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        n,pre = float('inf'),float('-inf')\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            nonlocal n\n",
    "            nonlocal pre\n",
    "            n = min(root.val-pre, n)\n",
    "            pre = root.val\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.minDiff = None\n",
    "        self.prev = None\n",
    "\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.prev = None\n",
    "        self.minDiff = 10e6\n",
    "        self.inOrder(root)\n",
    "        return self.minDiff\n",
    "\n",
    "    def inOrder(self, root: Optional[TreeNode]):\n",
    "        if not root:\n",
    "            return\n",
    "        self.inOrder(root.left)\n",
    "        if self.prev:\n",
    "            self.minDiff = min(root.val - self.prev.val, self.minDiff)\n",
    "        self.prev = root\n",
    "        self.inOrder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.all_value = []\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            self.all_value.append(root.val)\n",
    "            inorder(root.left)\n",
    "            inorder(root.right)\n",
    "            \n",
    "        inorder(root)\n",
    "        self.all_value.sort()\n",
    "        res = float('inf')\n",
    "        for i in range(1, len(self.all_value)):\n",
    "            res = min(res, abs(self.all_value[i] - self.all_value[i-1]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        last = -inf\n",
    "        ans = inf\n",
    "        def inorder(root):\n",
    "            nonlocal ans, last\n",
    "            if root is None:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            x = root.val\n",
    "            if last != -inf:\n",
    "                ans = min(ans, x - last)\n",
    "            last = x\n",
    "            inorder(root.right)\n",
    "        \n",
    "        inorder(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.all_value = []\n",
    "        def mi_order(root):\n",
    "            if not root:\n",
    "                return\n",
    "            mi_order(root.left)\n",
    "            self.all_value.append(root.val)\n",
    "            mi_order(root.right)\n",
    "            \n",
    "        mi_order(root)\n",
    "        res = float('inf')\n",
    "        for i in range(1, len(self.all_value)):\n",
    "            res = min(res, abs(self.all_value[i] - self.all_value[i-1]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.min = float('inf')\n",
    "        self.pre = float('-inf')\n",
    "        def inorder(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            inorder(node.left)\n",
    "            self.min = min(self.min, node.val-self.pre)\n",
    "            self.pre = node.val\n",
    "            inorder(node.right)\n",
    "        inorder(root)\n",
    "        return self.min\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = float(\"inf\")\n",
    "        self.pre = float(\"inf\")\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \n",
    "            dfs(root.left)\n",
    "            self.ans = min(self.ans, abs(root.val - self.pre))\n",
    "            self.pre = root.val\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.dfs(root.left)\n",
    "        self.result = min(root.val - self.last, self.result)\n",
    "        self.last = root.val\n",
    "        self.dfs(root.right)\n",
    "\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.last = -float('inf')\n",
    "        self.result = float('inf')\n",
    "        self.dfs(root)\n",
    "        return self.result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traversal(self, root, vec):\n",
    "        if root == None:\n",
    "            return\n",
    "        self.traversal(root.left, vec)\n",
    "        vec.append(root.val)\n",
    "        self.traversal(root.right, vec)\n",
    "\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        vec = []\n",
    "        self.traversal(root, vec)\n",
    "        ans = float('inf')\n",
    "        for i in range(0, len(vec) - 1):\n",
    "            if ans > vec[i + 1] - vec[i]:\n",
    "                ans = vec[i + 1] - vec[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.prev = float('-inf')\n",
    "        self.min = float('inf')\n",
    "\n",
    "        def inorder(node):\n",
    "            if not node:\n",
    "                return None\n",
    "\n",
    "            inorder(node.left)\n",
    "            self.min = min(self.min, node.val-self.prev)\n",
    "            self.prev = node.val\n",
    "            inorder(node.right)\n",
    "        inorder(root)\n",
    "        return self.min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root, values):\n",
    "            if root is None: return\n",
    "            dfs(root.left, values)\n",
    "            values.append(root.val)\n",
    "            dfs(root.right, values)\n",
    "        values = []\n",
    "        dfs(root, values)\n",
    "        # values.sort()\n",
    "        min_diff = 100000\n",
    "        for i in range(len(values)-1):\n",
    "            diff = values[i+1]-values[i]\n",
    "            if diff == 1: return 1\n",
    "            if diff < min_diff:\n",
    "                min_diff = diff\n",
    "        return min_diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.pre = float('-inf')\n",
    "        self.res = float('inf')\n",
    "        self.helper(root)\n",
    "\n",
    "        return self.res\n",
    "\n",
    "\n",
    "    def helper(self, node):\n",
    "        if node:\n",
    "            self.helper(node.left)\n",
    "            self.res = min(self.res, node.val - self.pre)\n",
    "            self.pre = node.val\n",
    "            self.helper(node.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        nums = []\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            item = stack.pop()\n",
    "            if item:\n",
    "                nums.append(item.val)\n",
    "                stack.append(item.left)\n",
    "                stack.append(item.right)\n",
    "        nums.sort()\n",
    "        return min(x - y for x, y in zip(nums[1:], nums[:-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, node):\n",
    "        if not node:\n",
    "            return []\n",
    "        return self.dfs(node.left) + [node.val] + self.dfs(node.right)\n",
    "\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        rs = self.dfs(root)\n",
    "        mini = 1+1e5\n",
    "        for i in range(len(rs)-1):\n",
    "            mini = min(mini,rs[i+1] - rs[i])\n",
    "        return mini\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        _list = []\n",
    "        def preOrder(root):\n",
    "            if not root:\n",
    "                return\n",
    "            preOrder(root.left)\n",
    "            _list.append(root.val)\n",
    "            preOrder(root.right)\n",
    "        preOrder(root)\n",
    "        min_d = math.inf\n",
    "        for idx in range(1,len(_list)):\n",
    "            min_d = min(min_d,_list[idx]-_list[idx-1])\n",
    "        return min_d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = inf\n",
    "        pre = None\n",
    "        def dfs(root):\n",
    "            if not root: \n",
    "                return\n",
    "            nonlocal ans\n",
    "            nonlocal pre\n",
    "            dfs(root.left)\n",
    "            if pre:\n",
    "                ans = min(ans, root.val - pre.val)\n",
    "            pre = root\n",
    "            dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = inf\n",
    "        def f(root,left,right):\n",
    "            nonlocal ans\n",
    "            if root is None: return \n",
    "            ans  = min(ans,min(abs(left-root.val),abs(right-root.val)))\n",
    "            f(root.left,left,root.val)\n",
    "            f(root.right,root.val,right)\n",
    "        f(root,-inf,inf)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self,root):\n",
    "        if(root == None):\n",
    "            return 0\n",
    "        self.dfs(root.left)\n",
    "        if(self.pre != None):\n",
    "            self.ans = min(self.ans,root.val - self.pre.val)\n",
    "        self.pre=root\n",
    "        self.dfs(root.right)\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.pre=None\n",
    "        self.ans=inf\n",
    "        self.dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = inf\n",
    "        pre = None\n",
    "        def dfs(root) -> None:\n",
    "            if not root:\n",
    "                return\n",
    "            # 先递归左子树\n",
    "            dfs(root.left)\n",
    "            #前置节点有值\n",
    "            nonlocal pre, ans\n",
    "            if pre:\n",
    "                ans = min(ans, root.val - pre.val)\n",
    "            pre = root\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\r\n",
    "        val_list = self.dfs(root)\r\n",
    "        # print(val_list)\r\n",
    "        ans = 10**5+10\r\n",
    "        for i in range(1, len(val_list)):\r\n",
    "            ans = min(ans, val_list[i]-val_list[i-1])\r\n",
    "        return ans\r\n",
    "\r\n",
    "    def dfs(self, root):\r\n",
    "        if root is None:\r\n",
    "            return []\r\n",
    "        val_list = list()\r\n",
    "        val_list.extend(self.dfs(root.left))\r\n",
    "        val_list.append(root.val)\r\n",
    "        val_list.extend(self.dfs(root.right))\r\n",
    "        return val_list\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.arr = []\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            self.arr.append(node.val)\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return min([(abs(self.arr[i] - self.arr[i - 1])) for i in range(1, len(self.arr))])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        order_list = self.bianli(root)\n",
    "        min_ = order_list[1] - order_list[0]\n",
    "        for i in range(len(order_list) - 1):\n",
    "            Diff = order_list[i + 1] - order_list[i]\n",
    "            if Diff < min_:\n",
    "                min_ = Diff\n",
    "        return min_\n",
    "    \n",
    "    def bianli(self, root: Optional[TreeNode]):\n",
    "        if not root:\n",
    "            return []\n",
    "        return self.bianli(root.left) + [root.val] + self.bianli(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            global p,a\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            if p==-1:\n",
    "                p=root.val\n",
    "            else:\n",
    "                a=min(a,root.val-p)\n",
    "                p=root.val\n",
    "            dfs(root.right)\n",
    "        global a,p\n",
    "        a=inf\n",
    "        p=-1\n",
    "        dfs(root)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre = None\n",
    "        self.result = float('inf')\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return self.result\n",
    "        self.minDiffInBST(root.left)\n",
    "\n",
    "        dif = abs(self.pre.val - root.val) if self.pre else self.result\n",
    "        if dif < self.result:\n",
    "            self.result = dif\n",
    "        self.pre = root\n",
    "\n",
    "        self.minDiffInBST(root.right)\n",
    "\n",
    "        return self.result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.prev = float('-inf')\n",
    "        self.min = float('inf')\n",
    "        def inorder(node):\n",
    "            if not node:\n",
    "                return None\n",
    "\n",
    "            inorder(node.left)\n",
    "            self.min = min(self.min, node.val-self.prev)\n",
    "            self.prev = node.val\n",
    "            inorder(node.right)\n",
    "        inorder(root)\n",
    "        return self.min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        arr=[]\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                dfs(node.left)\n",
    "                arr.append(node.val)\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "        ans=inf\n",
    "        for i in range(1,len(arr)):\n",
    "            ans=min(ans,arr[i]-arr[i-1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from typing import Optional\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.vals = []\n",
    "        self.inOrder(root)\n",
    "        return min([self.vals[i] - self.vals[i-1] for i in range(1,len(self.vals))])\n",
    "\n",
    "    def inOrder(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.inOrder(root.left)\n",
    "        self.vals.append(root.val)\n",
    "        self.inOrder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.min = float('inf')\n",
    "        self.prev = float('-inf')\n",
    "        \n",
    "        def inorder(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            inorder(node.left)\n",
    "            self.min = min(self.min, node.val-self.prev)\n",
    "            self.prev = node.val\n",
    "            inorder(node.right)\n",
    "        inorder(root)\n",
    "        return self.min\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        # 这里还有一个信息是，这是二叉树，左边比右边小，即左<中<右，所以可以用中序遍历进行展开\n",
    "        # 只需要比较左右即可，因为中序遍历以后，中间就没有其他的数值可能了\n",
    "        def mid_trade(node: Optional[TreeNode]):\n",
    "            res = [node.val]\n",
    "            if node.left: res = mid_trade(node.left) + res\n",
    "            if node.right: res = res + mid_trade(node.right)\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        node_list = mid_trade(root)\n",
    "        min_value = float(\"inf\")\n",
    "        for i in range(len(node_list)-1):\n",
    "            min_value = min(node_list[i+1]-node_list[i], min_value)\n",
    "        return min_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        mn = inf\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            # 无返回值\n",
    "            if not root: return\n",
    "            dfs(root.left)\n",
    "            res.append(root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        for i in range(len(res)-1):\n",
    "            mn = min(mn, abs(res[i]-res[i+1]))\n",
    "        return mn\n",
    "       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        ans=inf\n",
    "        pre=-100001\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            nonlocal ans,pre\n",
    "            x=root.val-pre\n",
    "            ans=min(ans,x)\n",
    "            pre=root.val\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 1e9\n",
    "        pre = -1\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            nonlocal pre\n",
    "            if node.left:\n",
    "                dfs(node.left)\n",
    "\n",
    "            if pre == -1:\n",
    "                pre = node.val\n",
    "            else:\n",
    "                ans = min(ans, abs(pre - node.val))\n",
    "                pre = node.val\n",
    "\n",
    "            if node.right:\n",
    "                dfs(node.right)\n",
    "            return\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        def pre(r):\n",
    "            if not r:\n",
    "                return []\n",
    "            else:\n",
    "                return [r.val]+pre(r.left)+pre(r.right)\n",
    "        a=pre(root)\n",
    "        a.sort()\n",
    "        res=a[1]-a[0]\n",
    "        for i in range(2,len(a)):\n",
    "            res=min(a[i]-a[i-1],res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre=None\n",
    "        self.result = float('inf')\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.traversal(root)\n",
    "        return self.result\n",
    "\n",
    "    def traversal(self,root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.traversal(root.left)\n",
    "        if self.pre:            \n",
    "            self.result=min(root.val-self.pre.val,self.result)\n",
    "        self.pre=root\n",
    "        self.traversal(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        stack = []\n",
    "        cur = root\n",
    "        pre = None\n",
    "        result = float('inf')\n",
    "\n",
    "        while cur is not None or len(stack) > 0:\n",
    "            if cur is not None:\n",
    "                stack.append(cur)  # 将访问的节点放进栈\n",
    "                cur = cur.left  # 左\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                if pre is not None:  # 中\n",
    "                    result = min(result, cur.val - pre.val)\n",
    "                pre = cur\n",
    "                cur = cur.right  # 右\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = float('inf')\n",
    "        self.pre = None\n",
    "\n",
    "    def traversal(self, cur):\n",
    "        if cur is None:\n",
    "            return\n",
    "        self.traversal(cur.left)  # 左\n",
    "        if self.pre is not None:  # 中\n",
    "            self.result = min(self.result, cur.val - self.pre.val)\n",
    "        self.pre = cur  # 记录前一个\n",
    "        self.traversal(cur.right)  # 右\n",
    "\n",
    "    def minDiffInBST(self, root):\n",
    "        self.traversal(root)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        val, _, _ = self.find(root)\n",
    "        return val\n",
    "    \n",
    "    def find(self, root):\n",
    "        if not root:\n",
    "            return 100001, -1, -1\n",
    "        l_min, L_max, L_min = self.find(root.left)\n",
    "        r_min, R_max, R_min = self.find(root.right)\n",
    "        if not root.left:\n",
    "            if not root.right:\n",
    "                return 100001, root.val, root.val\n",
    "            return min(r_min, abs(root.val - R_min)), R_max, root.val\n",
    "        if not root.right:\n",
    "            return min(l_min, abs(root.val - L_max)), root.val, L_min\n",
    "        else:\n",
    "            return min(l_min, r_min, abs(root.val - L_max), abs(root.val - R_min)), R_max, L_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        \"\"\"\n",
    "        中序遍历下的连续两个值极可能是最小差值\n",
    "        \"\"\"\n",
    "        self.prev = None\n",
    "        self.rs = float('inf')\n",
    "        def dfs (root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            if self.prev:\n",
    "                self.rs = min(self.rs,root.val-self.prev.val)\n",
    "            self.prev = root\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        value = []\n",
    "        def dfs(root):\n",
    "            # nonlocal value\n",
    "            if root:\n",
    "                value.append(root.val)\n",
    "            if root.left:\n",
    "                dfs(root.left)\n",
    "            if root.right:\n",
    "                dfs(root.right)\n",
    "        dfs(root)\n",
    "        value.sort()\n",
    "        ans = max(value)\n",
    "        for v1, v2 in pairwise(value):\n",
    "            ans = min(ans, abs(v1 - v2))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        queue = [root]\n",
    "        k = []\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            k.append(cur.val)            \n",
    "            if cur.left:\n",
    "                queue.append(cur.left)\n",
    "            if cur.right:\n",
    "                queue.append(cur.right)\n",
    "        k.sort()\n",
    "        n = len(k)\n",
    "        minnum = inf\n",
    "        for i in range(1,n):\n",
    "            minnum = min(minnum,k[i]-k[i-1])\n",
    "        return minnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        pre = -inf\n",
    "        ans = inf\n",
    "        def dfs(u):\n",
    "            if not u:\n",
    "                return\n",
    "            dfs(u.left)\n",
    "            nonlocal ans, pre\n",
    "            ans = min(ans, u.val - pre)\n",
    "            pre = u.val\n",
    "            dfs(u.right)\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        last_val = -inf\n",
    "        ans = inf\n",
    "\n",
    "        s = []\n",
    "        c = root\n",
    "        while s or c:\n",
    "            while c:\n",
    "                s.append(c)\n",
    "                c = c.left\n",
    "\n",
    "            n = s.pop()\n",
    "            c = n.right\n",
    "\n",
    "            v = n.val\n",
    "            ans = min(ans, v - last_val)\n",
    "            last_val = v\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "class TreeNode:\r\n",
    "    def __init__(self, val=0, left=None, right=None):\r\n",
    "        self.val = val\r\n",
    "        self.left = left\r\n",
    "        self.right = right\r\n",
    "\r\n",
    "from typing import Optional        \r\n",
    "class Solution:\r\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\r\n",
    "        self.prev = None\r\n",
    "        self.res = 10 ** 5\r\n",
    "\r\n",
    "        def inOrder(root):\r\n",
    "            if not root: return\r\n",
    "            inOrder(root.left)\r\n",
    "\r\n",
    "            if self.prev != None:\r\n",
    "                self.res = min(self.res, root.val - self.prev)\r\n",
    "            self.prev = root.val\r\n",
    "\r\n",
    "            inOrder(root.right)\r\n",
    "            return\r\n",
    "        \r\n",
    "        inOrder(root)\r\n",
    "        return self.res\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        stack = []\n",
    "        cur = root\n",
    "        pre = None\n",
    "        result = float('inf')\n",
    "        while cur or stack:\n",
    "            if cur: # 指针来访问节点，访问到最底层\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            else: # 逐一处理节点\n",
    "                cur = stack.pop()\n",
    "                if pre: # 当前节点和前节点的值的差值\n",
    "                    result = min(result, cur.val - pre.val)\n",
    "                pre = cur\n",
    "                cur = cur.right\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        a = []\n",
    "        def dfs(root: Optional[TreeNode])-> None:\n",
    "            if not root:\n",
    "                return None\n",
    "            a.append(root.val)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        a.sort()\n",
    "        return min(y - x for x, y in pairwise(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        # 二叉搜索树，所以LDR后相邻结点的最小差值即为目标\n",
    "        minus = 10 ** 9\n",
    "        self.res = []\n",
    "        def helper(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            if root.left is not None:\n",
    "                helper(root.left)\n",
    "            self.res.append(root.val)\n",
    "            if root.right is not None:\n",
    "                helper(root.right)\n",
    "        helper(root)\n",
    "        for i in range(len(self.res)-1):\n",
    "            m = abs(self.res[i] - self.res[i + 1])\n",
    "            minus = min(m, minus)\n",
    "        return minus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root, values):\n",
    "            if root is None: return\n",
    "            dfs(root.left, values)\n",
    "            values.append(root.val)\n",
    "            dfs(root.right, values)\n",
    "        values = []\n",
    "        dfs(root, values)\n",
    "        # values.sort()\n",
    "        min_diff = 100000\n",
    "        pre = values[0]\n",
    "        for value in values[1:]:\n",
    "            diff = value - pre\n",
    "            if diff == 1: return 1\n",
    "            if diff < min_diff:\n",
    "                min_diff = diff\n",
    "            pre = value\n",
    "        # for i in range(len(values)-1):\n",
    "        #     diff = values[i+1]-values[i]\n",
    "        #     if diff == 1: return 1\n",
    "        #     if diff < min_diff:\n",
    "        #         min_diff = diff\n",
    "        return min_diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, root, res):\n",
    "        if not root:\n",
    "            return None\n",
    "        self.dfs(root.left, res)\n",
    "        res.append(root.val)\n",
    "        self.dfs(root.right, res)\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        res = []\n",
    "        self.dfs(root, res)\n",
    "        ans = inf\n",
    "        for i in range(0, len(res) - 1):\n",
    "            ans = min(ans, res[i+1] - res[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:  \n",
    "    def dfs(self, root, pre, ans):  \n",
    "        if root is None:  \n",
    "            return  \n",
    "        self.dfs(root.left, pre, ans)  \n",
    "        if pre[0] == -1:  \n",
    "            pre[0] = root.val  \n",
    "        else:  \n",
    "            ans[0] = min(ans[0], root.val - pre[0])  \n",
    "            pre[0] = root.val  \n",
    "        self.dfs(root.right, pre, ans)  \n",
    "  \n",
    "    def minDiffInBST(self, root):  \n",
    "        ans = [float('inf')]  \n",
    "        pre = [-1]  \n",
    "        self.dfs(root, pre, ans)  \n",
    "        return ans[0]  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 100001\n",
    "        pre = -inf\n",
    "        def dfs(node):\n",
    "            if node == None:\n",
    "                return \n",
    "            \n",
    "            nonlocal ans\n",
    "            nonlocal pre\n",
    "            dfs(node.left)\n",
    "            ans = min(node.val-pre, ans)\n",
    "            pre = node.val\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "         # 深搜，广搜都可以，主要是拿到一个数值就开始比较\n",
    "        store_list = []\n",
    "        min_value = 100000\n",
    "        level_list = [root]\n",
    "        next_list = []\n",
    "        while level_list:\n",
    "            for new_node in level_list:\n",
    "                for node in store_list:\n",
    "                    min_value = min(min_value, abs(new_node.val - node.val))\n",
    "                store_list.append(new_node)\n",
    "                if new_node.left: next_list.append(new_node.left)\n",
    "                if new_node.right : next_list.append(new_node.right)\n",
    "            # 广搜\n",
    "            level_list = next_list\n",
    "            next_list = []\n",
    "        \n",
    "        return min_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        pre = None\n",
    "        ans = float('inf')\n",
    "        def f(root):\n",
    "            nonlocal pre,ans\n",
    "            if not root:return\n",
    "            f(root.left)\n",
    "            if pre:ans = min(ans,root.val - pre.val)\n",
    "            pre = root\n",
    "            f(root.right)\n",
    "        f(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        # 搜到全部的数字写到一个数组里面，然后排序，用pairwise解决\n",
    "        # 但是这道题是一个二叉搜索树，最小的在左子树，其次是根，然后是右子树\n",
    "        glob = []\n",
    "        def dfs(root): \n",
    "            if root.left :\n",
    "                dfs(root.left)\n",
    "            glob.append(root.val)\n",
    "            if root.right :\n",
    "                dfs(root.right)\n",
    "        dfs(root)\n",
    "        ans = 0x3f3f3f3f\n",
    "        for a,b in pairwise(glob):\n",
    "            ans = min(ans,abs(a-b)) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        result = []\n",
    "        res = inf\n",
    "        def mid(node):\n",
    "            if node == None:\n",
    "                return\n",
    "            mid(node.left)\n",
    "            result.append(node.val)\n",
    "            mid(node.right)\n",
    "        mid(root)\n",
    "        for i in range(len(result)-1):\n",
    "            res = min(result[i+1] - result[i], res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        self.vals = []\n",
    "        self.inOrder(root)\n",
    "        return min([self.vals[i + 1] - self.vals[i] for i in range(len(self.vals) - 1)])\n",
    "\n",
    "    def inOrder(self, root):\n",
    "        if not root:\n",
    "            return \n",
    "        self.inOrder(root.left)\n",
    "        self.vals.append(root.val)\n",
    "        self.inOrder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        ans, pre = float(\"inf\"), -1\n",
    "        stack = []\n",
    "        while root or stack:      \n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop(-1)\n",
    "            if pre == -1:\n",
    "                pre = root.val\n",
    "            else:\n",
    "                ans = min(ans,root.val - pre)\n",
    "                pre = root.val\n",
    "            root = root.right \n",
    "        return ans\n",
    "    # def minDiffInBST(self, root: TreeNode) -> int:\n",
    "    #     def in_order(prev, curr, m):\n",
    "    #         if not curr:\n",
    "    #             return prev, m\n",
    "    #         prev, m = in_order(prev, curr.left, m)\n",
    "    #         m, prev = min(m, curr.val - prev), curr.val\n",
    "    #         return in_order(prev, curr.right, m)\n",
    "    #     return in_order(-float(\"inf\"),root,float(\"inf\"))[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        # 使用递归\n",
    "        nums = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            return dfs(root.left) + [root.val] + dfs(root.right)\n",
    "        \n",
    "        nums = dfs(root)\n",
    "        res = float(\"inf\")\n",
    "        for i in range(len(nums)-1):\n",
    "            res = min(res,abs(nums[i+1]-nums[i]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        stack=[]\n",
    "        node=root\n",
    "        result=1E6\n",
    "        while node.left:\n",
    "            stack.append(node)\n",
    "            node=node.left\n",
    "        #寻找每个节点的下个节点\n",
    "        while True:\n",
    "            if node.right:\n",
    "                #有右节点，访问其右节点的最左子节点\n",
    "                stack.append(node)\n",
    "                nextnode=node.right\n",
    "                while nextnode.left:\n",
    "                    stack.append(nextnode)\n",
    "                    nextnode=nextnode.left\n",
    "            elif len(stack)==0:\n",
    "                #根节点且无右节点\n",
    "                break\n",
    "            else:\n",
    "                #无右节点，访问上一个自己是其左节点的父节点\n",
    "                nextnode=node\n",
    "                parent=stack.pop()\n",
    "                while parent.right==nextnode and len(stack)!=0:\n",
    "                    nextnode=parent\n",
    "                    parent=stack.pop()\n",
    "                else:\n",
    "                    if len(stack)==0 and parent.right==nextnode:\n",
    "                        break\n",
    "                    else:\n",
    "                        #此时parent.left=nextnode\n",
    "                        nextnode=parent\n",
    "            result=min(result,nextnode.val-node.val)\n",
    "            node=nextnode\n",
    "        return result\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        def recur(root):\n",
    "            min_val,max_val=root.val,root.val\n",
    "            result=1000000000000\n",
    "            if root.left:\n",
    "                min_val,l_max_val,l_result=recur(root.left)\n",
    "                result=min(result,l_result,root.val-l_max_val)\n",
    "            if root.right:    \n",
    "                r_min_val,max_val,r_result=recur(root.right)\n",
    "                result=min(result,r_result,r_min_val-root.val)\n",
    "            return min_val,max_val,result\n",
    "        \n",
    "        min_val,max_val,result=recur(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        # 搜到全部的数字写到一个数组里面，然后排序，用pairwise解决\n",
    "        glob = []\n",
    "        def dfs(root): \n",
    "            glob.append(root.val)\n",
    "            if root.left :\n",
    "                dfs(root.left)\n",
    "            if root.right :\n",
    "                dfs(root.right)\n",
    "        dfs(root)\n",
    "        glob.sort()\n",
    "        ans = 0x3f3f3f3f\n",
    "        for a,b in pairwise(glob):\n",
    "            ans = min(ans,abs(a-b)) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "\n",
    "        tmp = []\n",
    "        prev = None\n",
    "        res = float('inf')\n",
    "        def inorder(node):\n",
    "\n",
    "            if not node: return \n",
    "            inorder(node.left)\n",
    "            nonlocal prev, res\n",
    "            if prev:\n",
    "                res = min(res, abs(prev.val - node.val))\n",
    "            prev = node\n",
    "            inorder(node.right)\n",
    "\n",
    "        inorder(root)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDiffInBST(self, root: Optional[TreeNode]) -> int:\n",
    "        val = 10**5\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            res.append(root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        for i in range(1, len(res)):\n",
    "            val = min(val, res[i] - res[i-1])\n",
    "        return val"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
